1. Field of the Invention
This invention relates to computing systems and more particularly to data prefetching of computing systems.
2. Description of the Related Art
Referring to FIG. 1, a typical hierarchical memory system (e.g., memory system 10) includes a cache (e.g., cache 13), a main memory (e.g., main memory 20), a cache control circuit (e.g., cache controller 22), and one or more execution units and/or one or more processors (e.g., processor 12). The execution unit or processor, cache control circuit, and cache may reside on one or more integrated circuits. Cache 13 may be a multi-level cache (e.g., a three-level cache, as shown in FIG. 1). In general, the storage capacity of individual levels of a multi-level cache increases with increasing cache level while the cost and speed decrease with increasing cache level. The term “cache,” as used hereinafter, refers to at least one level of a cache (e.g., level-1 of a three-level cache), unless otherwise specified. Cache controller 22 is a circuit, sub-circuit, or other device that controls the state of a corresponding cache. Although cache controller 22 is illustrated as being separate from processor 12, cache 13, and main memory 20, a cache control circuit may be included, for example, as part of a cache, execution unit or processor, or other portion of a system including a cache.
Due to a limited, although large, cache size, only a portion of the data available to the execution unit or processor can reside in the cache at a particular time. When the processor attempts to access a specific location in main memory, the processor first determines whether or not the contents of a particular memory location are present in the cache. If the contents of the particular location in main memory are present in the cache, a “cache hit” occurs and the processor fetches the contents of the particular location in memory from the cache. If the contents of the particular location in main memory are not present in the cache, a “cache miss” occurs and the processor fetches the contents from main memory.